As is well known, a solid state drive (SSD) is a data storage device that uses a NAND-based flash memory to store data. The NAND-based flash memory is a non-volatile memory. After data are written to the flash memory, if no power is supplied to the flash memory, the data are still retained in the flash memory.
FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controlling unit 101, a cache memory 107, and a flash memory 105. In the solid state drive 10, the controlling unit 101 is in communication with the flash memory 105 and the cache memory 107 for controlling the data accessing operations of the flash memory 105 and the cache memory 107. In addition, the controlling unit 101 is in communication with a host 12 through an external bus 20. Consequently, commands and data can be exchanged between the controlling unit 101 and the host 12. Generally, the external bus 20 is a USB bus, an IEEE 1394 bus, a PCIe bus, an SATA bus, or the like.
Generally, the flash memory 105 comprises a plurality of blocks. Each block comprises a plurality of pages (or sectors), for example 128 pages. Each page is typically 8K bytes in size. Due to the inherent properties of the flash memory 105, at least one page is written at a time during the writing operation is performed, and the erasing operation is performed in a block-wise fashion.
Generally, the cache memory 107 is a buffering unit for temporarily storing the write data which is inputted through the host 12 or storing the read data which is outputted from the flash memory 105. In a case that no power is supplied to the cache memory 107, the data in the cache memory 107 will be deleted. The cache memory 107 is for example a static random access memory (SRAM) or a dynamic random access memory (DRAM). Since the cache memory 107 is acted as the buffering unit for the flash memory 105, the controlling unit 101 should efficiently manage the cache memory 107 while maintaining the data consistency between the cache memory 107 and the flash memory 105.
Basically, the cache memory 107 comprises a plurality of cache units. Each cache unit corresponds to an address. The cache units are managed by the controlling unit 101 through a cache link list.
FIG. 2 schematically illustrates a cache link list for the cache units of the conventional solid state drive. As shown in FIG. 2, each cache unit has a fixed address (A1˜A8). The storage capacity of the data in the cache unit is equal to the size of one page for example. For each cache unit, the address of the previous cache unit, the address of the next cache unit, the status of the cache unit itself and the logical allocation address (LAA) of the flash memory 105 corresponding to the cache unit are recorded in the cache link list. Moreover, the status of the cache unit may include a free status, a write status, a read status, a need fill-up status, and a lock status.
In a case that no data or an invalid data is stored in the cache unit (e.g. the cache unit corresponding to address A8 or A1), the cache unit is in the free status. Under this circumstance, the cache unit can temporarily store the write data which is inputted through the host 12 or store the read data which is outputted from the flash memory 105.
In a case that the data of a complete page from the host 12 is temporarily stored in the cache unit (e.g. the cache unit corresponding to address A3 or A7), the cache unit is in the write status. Meanwhile, the data in these two cache units have not been written into the flash memory 105. Whereas, the data in these two cache units will be respectively written into the logical allocation addresses P1 and P4 of the flash memory 105.
In a case that the data of a partial page from the host 12 is temporarily stored in the cache unit (e.g. the cache unit corresponding to address A4), the cache unit is in the need fill-up status. Meanwhile, the data in the partial page has not been written into the flash memory 105. Whereas, after the data in the partial page has been processed, the data will be written into the logical allocation address P3 of the flash memory 105.
In a case that the data from the flash memory 105 is temporarily stored in the cache unit (e.g. the cache unit corresponding to address A2 or A6), the cache unit is in the read status. The read data have been transmitted from the logical allocation addresses P2 and P5 of the flash memory 105 to the cache units and the host 12.
In a case that the cache unit (e.g. the cache unit corresponding to address A5) is being processed by the controlling unit 101, the cache unit is in the lock status. Meanwhile, the data in the logical allocation address P6 of the flash memory 105 is being processed. Consequently, the data fails to be read from or written into this cache unit at this moment.
From the above discussions, in the conventional solid state drive 10, the cache units of the cache memory 107 are managed by the controlling unit 101 according to the cache link list. That is, the conventional cache memory utilizes the single cache link list to link all of cache units.
However, the way to use the single cache link list may deteriorate the performance of the controlling unit 101. For example, during a write back action is performed by the controlling unit 101, the cache units in the write state will be firstly searched, and then the data in these cache units are written back to the flash memory according to the logical allocation addresses (LAAs). Since the cache units are managed by the controlling units 101 according to the single cache link list, the controlling unit 101 may only sequentially search the write-status cache units starting from the first cache unit. Under this circumstance, the performance of the controlling unit 101 is largely impaired.
Similarly, in a case that controlling unit 101 wants to search the cache units in another status, it is necessary to search these cache units starting from the first cache unit. That is, the performance of the controlling unit 101 and the solid state drive 10 will be impaired.